package leetcode.median;

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

/**
 * ClassName: $210_FindOrder
 * Description:
 * date: 2021-12-16 9:35
 *
 * @author liyifan
 */
public class $210_FindOrder {
    ArrayList<Integer> path;
    boolean[] onPath;
    boolean[] visited;
    boolean hasCycle;
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        path = new ArrayList<>();
        onPath = new boolean[numCourses];
        visited = new boolean[numCourses];
        List<Integer>[] graph = buildGraph(numCourses, prerequisites);

        for (int i = 0;i < numCourses;i++) {
            traverse(graph, i);
        }
        if (hasCycle) {
            return new int[]{};
        }
        Collections.reverse(path);
        int[] res = new int[numCourses];
        for (int i = 0;i < numCourses;i++) {
            res[i] = path.get(i);
        }
        return res;
    }

    public List<Integer>[] buildGraph(int numCourses, int[][] prerequisites) {
        List<Integer>[] graph = new LinkedList[numCourses];
        for (int i = 0;i < numCourses;i++) {
            graph[i] = new LinkedList<>();
        }
        for (int[] edge:prerequisites) {
            int from = edge[1];
            int to = edge[0];

            graph[from].add(to);
        }
        return graph;
    }

    public void traverse(List<Integer>[] graph, int s) {
        if (onPath[s]) {
            hasCycle = true;
        }
        if (visited[s] || hasCycle) {
            return;
        }
        visited[s] = true;
        onPath[s] = true;
        for (int v:graph[s]) {
            traverse(graph, v);
        }
        path.add(s);
        onPath[s] = false;
    }
}
